/**
 * 项目名称: Topic_169.cpp
 * 项目路径: study/DataStructure/刷题/一轮/第五天 数组+散列表
 * 编辑时间: 2024年09月06日07时57分09秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    struct Node{
        int val;
        int cnt;
    };
    Node h[200003];
    int find(int x){
        int t = (x %200003 + 200003)%200003;
        while (h[t].val!=0x3f3f3f3f && h[t].val!=x){
            t++;
            if(t==200003)t=0;
        }
        return t;
    }
    void init(){
        for(int i = 0;i< sizeof(h)/4;i++)
            h[i].val=0x3f3f3f3f;
    }
    int majorityElement(vector<int>& nums) {
        init();
        for(auto x:nums){
            int add = find(x);
            if(h[add].val == 0x3f3f3f3f){
                h[add].val=x;
            }
            h[add].cnt++;
        }
        int result = 0;
        for(int i = 0;i<sizeof(h)/8;i++)
            if(h[i].cnt > nums.size()/2)result= h[i].val;
        return result;
    }
};
